package code201_300.code20_30;


import java.util.Stack;

/**
 * 翻转一棵二叉树
 */
public class _226invertTree {

    /**
     * 思考：这次真是一个动态规划问题，原问题通过划分为无数子问题求解即可
     * 其实通过后序遍历即可，后序遍历过程中把每个节点转换一下，最终返回最后节点
     *
     * 卧槽！一次跑通！
     *
     * 执行用时：     * 0 ms     * , 在所有 Java 提交中击败了     * 100.00%     * 的用户
     * 内存消耗：     * 35.9 MB     * , 在所有 Java 提交中击败了     * 66.89%     * 的用户
     *
     * @param root
     * @return
     */
    public TreeNode invertTree(TreeNode root) {
        // 先过滤初始条件
        if(root==null||(root.left==null&&root.right==null))return root;
        Stack<TreeNode> stack = new Stack<>();
        Stack<TreeNode> revertStack = new Stack<>();
        TreeNode node = root;
        stack.push(node);
        // 先获取到根右左
        while (stack.size()!=0){
            node = stack.pop();
            revertStack.push(node);
            if(node.left!=null)stack.push(node.left);
            if(node.right!=null)stack.push(node.right);
        }
        // 反转为左右跟，刚好每个节点都反转一下
        while (revertStack.size() != 0){
            node = revertStack.pop();
            revertLeftAndRight(node);
        }
        return node;
    }

    /**
     * 此方法更换节点的左右子树
     */
    public TreeNode revertLeftAndRight(TreeNode node){
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
        return node;
    }

    /**
     * 官方题解：递归
     * 执行用时：     * 0 ms     * , 在所有 Java 提交中击败了     * 100.00%     * 的用户
     * 内存消耗：     * 35.7 MB     * , 在所有 Java 提交中击败了     * 80.33%     * 的用户
     *
     * 此方法好像复杂度更小，证明上述代码可在优化。但官方代码及其优雅，缺点就是递归不允许数据量特别大
     *
     * @param root
     * @return
     */
    public TreeNode invertTree1(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }

}
